package shortestPath;
//425185

public class BellmanFordLimon {
	public static long ShortestPathTo(int[][] matrix, boolean showAnswer) {
		long startTime = System.currentTimeMillis();
		
		int max = 1<<29, len = matrix.length, temp, changed;
		int[][] dist = new int[len][len];
		for(int i=0; i<dist.length; i++)
			for(int j=0; j<dist[0].length; j++) dist[i][j] = max;
		dist[0][0] = matrix[0][0];
		
		do {
			changed=0;
			for(int x=0; x<len; x++)
				for(int y=0; y<len; y++){
					if(y>0 && (temp=dist[y][x] + matrix[y-1][x]) < dist[y-1][x]) {	
						dist[y-1][x] = temp;
						changed++;
					}
					
					if(y<len-1 && (temp=dist[y][x] + matrix[y+1][x]) < dist[y+1][x]) {	
						dist[y+1][x] = temp;
						changed++;
					}
					
					if(x>0 && (temp=dist[y][x] + matrix[y][x-1]) < dist[y][x-1]) {	
						dist[y][x-1] = temp;
						changed++;
					}
					
					if(x<len-1 && (temp=dist[y][x] + matrix[y][x+1]) < dist[y][x+1]) {	
						dist[y][x+1] = temp;
						changed++;
					}
				}	
		} while(changed>0);
				
		
		
		if(showAnswer) System.out.println(dist[len-1][len-1]);
		return (System.currentTimeMillis()-startTime);
	}
}
